package dp;

/**
 * 求数组最长递增子数组，子数组不要求元素连续
 * 用动态规划来求解
 * R[i]表示以i号元素结尾的最长子序列长度，易知递推公式为：
 * 1）R[i]=1; 若i=0
 * 2）R[i]=max(R[k]}+1; k<i且A[k]<=A[i]，即R[i]为以所有前面比它小的元素为结尾的最长的序列长度+1
 * 3）R[i]=1; 若前面没有比它小的元素;
 *
 * @author zj
 */
public class LongestAscSubArray {
    //public static int A[] = {7,8,2,9,3,4,5,1};
    public static int A[] = {1, -1, 2, -3, 4, -5, 6, -7};

    public static void main(String args[]) {
        System.out.println(solution(A));
    }

    /**
     * @param arr
     */
    public static int solution(int arr[]) {
        if (arr == null || arr.length == 0) {
            return 0;
        }
        int tmp[] = new int[arr.length];
        tmp[0] = 1;  //边界条件，以第一个元素结尾的最长递增子序列就是该元素本身，必然为1
        int globalMax = 1;
        for (int i = 1; i < arr.length; i++) {
            int max = 0;
            for (int j = i - 1; j >= 0; j--) {
                if (arr[j] <= arr[i] && tmp[j] > max) {
                    max = tmp[j];
                }
            }
            if (max > 0) {
                tmp[i] = max + 1;
            } else {
                tmp[i] = 1;
            }
            globalMax = Math.max(globalMax, tmp[i]);
        }
        for (int i = 0; i < tmp.length; i++) {
            System.out.print(tmp[i] + " ");
        }
        System.out.println();
        return globalMax;
    }
}
